package main

import "unicode"

// 暴力解法，找到所有子串
// 1. 可以采用两个集合，分别记录出现过的大小字母，判断长度是否相等
// 2. 官方题解采用二进制来表示。
// 3. 如果多个答案，优先选择前面的，也就是 开始字符尽量靠前，和暴力破解，i j 顺序是一样的。
func longestNiceSubstring(s string) (ans string) {
	for i := range s {
		lower, upper := 0, 0
		for j := i; j < len(s); j++ {
			// 1. 判断是大小写字母
			if unicode.IsLower(rune(s[j])) {
				// 或运算，该位置变为1
				lower |= 1 << (s[j] - 'a')
			} else {
				upper |= 1 << (s[j] - 'A')
			}
			// 2. 如果是美好字符串，且长度大于 ans（不包含等于，等于的情况是后出现的）
			if lower == upper && j-i+1 > len(ans) {
				// 取结果
				ans = s[i : j+1]
			}
		}
	}
	return
}

// 分治法解决查看 395. 至少有 K 个重复字符的最长子串 思路
// 分治法
// 注意里面位运算的使用
func longestNiceSubstring(s string) (ans string) {
	// 1. 空串直接返回
	if s == "" {
		return
	}
	// 2. 判断是否是完美串，是的话直接返回
	lower, upper := 0, 0
	for _, ch := range s {
		if unicode.IsLower(ch) {
			lower |= 1 << (ch - 'a')
		} else {
			upper |= 1 << (ch - 'A')
		}
	}
	if lower == upper {
		return s
	}
	// 3. 执行 与操作，得到所有是 完美字符的二进制位
	valid := lower & upper
	for i := 0; i < len(s); i++ {
		// 开始执行遍历， i定格在 不是完美字符的位置， s[start:i] 来进行下轮判断
		start := i
		// 后面的操作，就是用来判断当前位置 是否是1， 不是1，说明当前字符，不是完美字符（不存在大写或小写）
		for i < len(s) && valid>>(unicode.ToLower(rune(s[i]))-'a')&1 == 1 {
			i++
		}
		// 找到分割得字符串，求出当前区间的最大完美字符串
		if t := longestNiceSubstring(s[start:i]); len(t) > len(ans) {
			ans = t
		}
	}
	// 4. 返回结果
	return
}
